package com.leetcode.根据算法进行分类.单调队列相关;


import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author: xiaomi
 * @date: 2021/2/14
 * @description:    剑指 Offer 59 - II. 队列的最大值
 * https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/
 * 之前有一道题是利用栈求出当前元素中的最大值。
 * 但是一到队列中暂时木有了头绪。
 */
public class B_剑指Offer59_II_队列的最大值 {

    public static void main(String[] args) {

    }

    /**
     * 设计的精髓：
     * 1.类似用 栈来保存当前元素中的最大值 的思想；
     * 2.使用一个单调双端队列来辅助实现 O(1) 的 max_value
     */
    static class MaxQueue {

        /**
         * 一个普通队列
         */
        Queue<Integer> queue = new LinkedList<>();
        /**
         * 双端队列进行辅助
         */
        Deque<Integer> deque = new LinkedList<>();


        public MaxQueue() {

        }

        public int max_value() {
            if (queue.isEmpty()){
                return -1;
            }
            return deque.peekFirst();
        }

        public void push_back(int value) {
            queue.offer(value);
            while (!deque.isEmpty() && deque.peekLast()<value){
                deque.removeLast();
            }
            deque.addLast(value);
        }

        public int pop_front() {
            if (queue.isEmpty()){
                return -1;
            }
            Integer res = queue.poll();
            if (deque.peekFirst().equals(res)){
                deque.removeFirst();
            }
            return res;
        }
    }
}
